package com.beiding.editanalyzeframe;

import java.util.ArrayList;
import java.util.List;

/**
 * 最大相似
 * @author 丁常磊
 * @date 2022/9/9 14:22
 */

public class MaxSameEditPossibility implements EditPossibility {


    @Override
    public double editPossibility(String a, String b) {

            //相等直接返回1
            if (a.equals(b)) {
                return 1;
            }

            //相似度为0
            if ("".equals(a) || "".equals(b)) {
                return 0;
            }

            //最大得分
            List<MaxPoint> maxPoints = new ArrayList<>();

            //转为列表
            char[] ca = a.toCharArray();

            //转为列表
            char[] cb = b.toCharArray();

            //评分矩阵
            int[][] w = new int[ca.length][];

            for (int i = 0; i < ca.length; i++) {
                //创建第二维对象 可能被其他行初始化 所以做一下判断
                if (w[i] == null) {
                    w[i] = new int[cb.length];
                }
                for (int j = 0; j < cb.length; j++) {
                    //如果两个元素相等
                    if (ca[i] == cb[j]) {

                        //累加当前的值
                        int v = ++w[i][j];

                        boolean currentMax = false;

                        //给右下节点累计当前节点的值
                        if (i < ca.length - 1 && j < cb.length - 1) {
                            int ni = i + 1;
                            int nj = j + 1;

                            if (ca[ni] == cb[nj]) {
                                //初始化下一元素
                                if (w[ni] == null) {
                                    w[ni] = new int[cb.length];
                                }

                                //传递当前节点的值
                                w[ni][nj] = v;
                            } else {
                                //当前节点最大
                                currentMax = true;
                            }

                        } else {
                            currentMax = true;
                        }

                        //如果当前节点已经最大
                        if (currentMax) {

                            //创建一个计算节点
                            MaxPoint maxPoint = new MaxPoint();
                            maxPoint.xStart = i - v + 1;
                            maxPoint.yStart = j - v + 1;
                            maxPoint.xEnd = i;
                            maxPoint.yEnd = j;
                            maxPoint.len = v;
                            maxPoint.sumMax = v;
                            maxPoints.add(maxPoint);
                        }

                    }
//                System.out.print(" "+w[i][j]);

                }

//            System.out.println();

            }


            //无任何相似
            if (maxPoints.size() == 0) {
                return 0;
            }

            //对计算节点排序,使 如果B能完全闭包A 则B一定在A后面
            SortUtils.sort(maxPoints, (pa, pb) -> {

                //闭包计算
                if (pb.xStart > pa.xEnd && pb.yStart > pa.yEnd) {
                    return 1;
                } else if (pa.xStart > pb.xEnd && pa.yStart > pb.yEnd) {
                    return -1;
                }

                //其余清空忽略
                return 0;

            });

        /*
            最后寻找最长路线
         */


            int max = 0;

            MaxPoint maxLinePoint = null;

            for (int i = 0; i < maxPoints.size(); i++) {
                //判断当前节点是否可以完全闭包
                MaxPoint current = maxPoints.get(i);

                //寻找前置完全可以闭包且最大的节点
                MaxPoint maxPre = null;
                for (int j = i - 1; j >= 0; j--) {
                    MaxPoint check = maxPoints.get(j);
                    //可以完全闭包
                    if (current.xStart > check.xEnd && current.yStart > check.yEnd) {
                        if (maxPre == null) {
                            maxPre = check;
                        } else {
                            if (check.sumMax > maxPre.sumMax) {
                                maxPre = check;
                            }
                        }
                    }
                }
                if (maxPre != null) {
                    //将前置数数字累加到自身
                    current.sumMax = current.len + maxPre.sumMax;
                }
                if (current.sumMax > max) {
                    maxLinePoint = current;
                    max = current.sumMax;
                }

            }

//        System.out.println(maxLinePoint);

            return maxLinePoint.sumMax * 2.0 / (a.length() + b.length());

        }



    private static class MaxPoint {
        private int xStart;
        private int xEnd;
        private int yStart;
        private int yEnd;
        private int sumMax;
        private int len;


        /**
         * 前置节点
         */
//        private MaxPoint maxPre;
    }


    }
